using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[] arr = new int[10];
            Random rd = new Random();
            for (int i = 0; i < 10; i++)
            {
                arr[i] = rd.Next(20);
            }
            string ss = arr.Max(p => p.ToString());
            int[] array = { 1, 2, 3, 4, 5, 0, 9, 8, 7, 6 };
            //BubbleSort(arr);
            SelectionSort(arr);
        }

        #region 冒泡排序
        /// <summary>
        /// 冒泡排序（从小到大）
        /// </summary>
        /// <param name="array"></param>
        public static void BubbleSort(int[] array)
        {
            for (int i = 0; i < array.Length - 1; i++)
            {
                for (int j = 0; j < array.Length - 1 - i; j++)
                {
                    if (array[j] > array[j + 1])
                    {
                        int temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
        }
        #endregion

        #region 选择排序
        /// <summary>
        /// 选择排序（从小到大）
        /// </summary>
        /// <param name="array"></param>
        public static void SelectionSort(int[] array)
        {
            int minIndex, temp;
            for (int i = 0; i < array.Length; i++)
            {
                minIndex = i;
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[j] < array[minIndex])
                    {
                        minIndex = j;
                    }
                }
                temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
        }
        #endregion

        #region 插入排序
        /// <summary>
        /// 插入排序（从小到大）
        /// </summary>
        /// <param name="array"></param>
        public static void InsertSort(int[] array)
        {
            for (int i = 1; i < array.Length; i++)
            {
                int temp = array[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (array[j] > temp)
                    {
                        array[j + 1] = array[j];
                        array[j] = temp;
                    }
                    else
                    {
                        break;
                    }
                }
            }
        }
        #endregion

        #region 希尔排序
        /// <summary>
        /// 希尔排序
        /// </summary>
        /// <param name="array"></param>
        public static void ShellSort(int[] array)
        {
            int length = array.Length;
            int temp;
            for (int step = length / 2; step >= 1; step /= 2)
            {
                for (int i = step; i < length; i++)
                {
                    temp = array[i];
                    int j = i - step;
                    while (j >= 0 && array[j] > temp)
                    {
                        array[j + step] = array[j];
                        j -= step;
                    }
                    array[j + step] = temp;
                }
            }
        }
        #endregion

        #region 归并排序
        /// <summary>
        /// 归并排序
        /// </summary>
        /// <param name="list"></param>
        /// <returns></returns>
        public static List<int> MergeSort(List<int> list)
        {
            if (list.Count <= 1)
            {
                return list;
            }
            int mid = list.Count / 2;
            List<int> left = new List<int>(); // 左侧list
            List<int> right = new List<int>(); // 右侧list
            for (int i = 0; i < mid; i++)
            {
                left.Add(list[i]);
            }
            for (int j = mid; j < list.Count; j++)
            {
                right.Add(list[j]);
            }
            left = MergeSort(left);
            right = MergeSort(right);
            return merge(left, right);
        }

        private static List<int> merge(List<int> left, List<int> right)
        {
            List<int> temp = new List<int>();
            while (left.Count > 0 && right.Count > 0)
            {
                if (left[0] <= right[0])
                {
                    temp.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    temp.Add(right[0]);
                    right.RemoveAt(0);
                }
            }
            if (left.Count > 0)
            {
                temp.AddRange(left);
            }
            else
            {
                temp.AddRange(right);
            }
            return temp;
        }
        #endregion


    }
}
